﻿/**
 * Copyright (C) 2013 original author and authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NGuice.Inject.Internal.Util
{
    public class ImmutableDictionaryBuilder<K, V>
    {
        readonly List<KeyValuePair<K, V>> entries = Lists.NewArrayList<KeyValuePair<K, V>>();

        /**
         * Creates a new builder. The returned builder is equivalent to the builder
         * generated by {@link ImmutableMap#builder}.
         */
        public ImmutableDictionaryBuilder() { }

        /**
         * Associates {@code key} with {@code value} in the built map. Duplicate
         * keys are not allowed, and will cause {@link #build} to fail.
         */
        public ImmutableDictionaryBuilder<K, V> Put(K key, V value)
        {
            entries.Add(ImmutableDictionary<K, V>.EntryOf(key, value));
            return this;
        }

        /**
         * Associates all of {@code map's} keys and values in the built map.
         * Duplicate keys are not allowed, and will cause {@link #build} to fail.
         *
         * @throws NullPointerException if any key or value in {@code map} is null
         */
        public ImmutableDictionaryBuilder<K, V> PutAll(IDictionary<K, V> map)
        {
            foreach (KeyValuePair<K, V> entry in map)
            {
                Put(entry.Key, entry.Value);
            }
            return this;
        }

        // TODO: Should build() and the ImmutableBiMap version throw an
        // IllegalStateException instead?

        /**
         * Returns a newly-created immutable map.
         *
         * @throws IllegalArgumentException if duplicate keys were added
         */
        public ImmutableDictionary<K, V> Build()
        {
            return FromEntryList(entries);
        }

        private static ImmutableDictionary<K, V> FromEntryList(List<KeyValuePair<K, V>> entries)
        {
            int size = entries.Count;
            switch (size)
            {
                case 0:
                    return ImmutableDictionary<K, V>.Of();
                case 1:
                    return new ImmutableDictionary<K,V>.SingletonImmutableDictionary<K, V>(entries[0]);
                default:
                    KeyValuePair<K, V>[] entryArray = entries.ToArray();
                    return new ImmutableDictionary<K, V>.RegularImmutableDictionary(entryArray);
            }
        }
    }

    /// <summary>
    /// 不可变字典的实现
    /// </summary>
    /// <typeparam name="TKey"></typeparam>
    /// <typeparam name="TValue"></typeparam>
    public abstract class ImmutableDictionary<TKey, TValue> : ConcurrentMap<TKey, TValue>
    {
        private static readonly ImmutableDictionary<TKey, TValue> EMPTY_IMMUTABLE_MAP = new EmptyImmutableDictionary();

        /// <summary>
        /// 获取空字典。
        /// </summary>
        /// <returns></returns>
        public static ImmutableDictionary<TKey, TValue> Of()
        {
            return EMPTY_IMMUTABLE_MAP;
        }

        /// <summary>
        /// 获取包含单个对象的不可变字典
        /// </summary>
        /// <param name="k1"></param>
        /// <param name="v1"></param>
        /// <returns></returns>
        public static ImmutableDictionary<TKey, TValue> Of(TKey k1, TValue v1)
        {
            return new SingletonImmutableDictionary<TKey, TValue>(Preconditions.CheckNotNull(k1), Preconditions.CheckNotNull(v1));
        }

        public static ImmutableDictionary<TKey, TValue> Of(TKey k1, TValue v1, TKey k2, TValue v2)
        {
            return new RegularImmutableDictionary(EntryOf(k1, v1), EntryOf(k2, v2));
        }

        internal static KeyValuePair<TKey, TValue> EntryOf(TKey key, TValue value)
        {
            return new KeyValuePair<TKey, TValue>(Preconditions.CheckNotNull(key), Preconditions.CheckNotNull(value));
        }

        public static ImmutableDictionary<TKey, TValue> Of(TKey k1, TValue v1, TKey k2, TValue v2, TKey k3, TValue v3)
        {
            return new RegularImmutableDictionary(EntryOf(k1, v1), EntryOf(k2, v2), EntryOf(k3, v3));
        }

        public static ImmutableDictionary<TKey, TValue> Of(TKey k1, TValue v1, TKey k2, TValue v2, TKey k3, TValue v3, TKey k4, TValue v4)
        {
            return new RegularImmutableDictionary(EntryOf(k1, v1), EntryOf(k2, v2), EntryOf(k3, v3), EntryOf(k4, v4));
        }

        public static ImmutableDictionary<TKey, TValue> Of(
            TKey k1, TValue v1, TKey k2, TValue v2, TKey k3, TValue v3, TKey k4, TValue v4, TKey k5, TValue v5)
        {
            return new RegularImmutableDictionary(EntryOf(k1, v1),
              EntryOf(k2, v2), EntryOf(k3, v3), EntryOf(k4, v4), EntryOf(k5, v5));
        }

        public static ImmutableDictionaryBuilder<TKey, TValue> Builder()
        {
            return new ImmutableDictionaryBuilder<TKey, TValue>();
        }

        public static ImmutableDictionary<TKey, TValue> CopyOf(IDictionary<TKey, TValue> map)
        {
            if (map is ImmutableDictionary<TKey, TValue>)
            {
                // safe since map is not writable
                ImmutableDictionary<TKey, TValue> kvMap = (ImmutableDictionary<TKey, TValue>)map;
                return kvMap;
            }

            int size = map.Count;
            switch (size)
            {
                case 0:
                    return ImmutableDictionary<TKey, TValue>.Of();
                case 1:
                    IEnumerator<KeyValuePair<TKey, TValue>> itera = map.GetEnumerator();
                    itera.MoveNext();
                    KeyValuePair<TKey, TValue> loneEntry = itera.Current;
                    /*
                     * Must cast next line to (K) and (V) to avoid returning an
                     * ImmutableMap<? extends K, ? extends V>, which is incompatible
                     * with the return type ImmutableMap<K, V>.  (Eclipse will complain
                     * mightily about this line if there's no cast.)
                     */
                    return ImmutableDictionary<TKey, TValue>.Of(loneEntry.Key, loneEntry.Value);
                default:
                    KeyValuePair<TKey, TValue>[] array = new KeyValuePair<TKey, TValue>[size];
                    int i = 0;
                    foreach (KeyValuePair<TKey, TValue> entry in map)
                    {
                        /*
                         * See comment above re: <? extends K, ? extends V> to <K, V>.
                         */
                        array[i++] = ImmutableDictionary<TKey, TValue>.EntryOf(entry.Key, entry.Value);
                    }
                    return new RegularImmutableDictionary(array);
            }
        }

        private ImmutableDictionary() { }

        public TValue PutIfAbsent(TKey key, TValue value)
        {
            throw new NotSupportedException();
        }

        public bool Remove(TKey key, TValue value)
        {
            throw new NotSupportedException();
        }

        public bool Remove(TKey key)
        {
            throw new NotSupportedException();
        }

        public bool Replace(TKey key, TValue oldValue, TValue newValue)
        {
            throw new NotSupportedException();
        }

        public TValue Replace(TKey key, TValue value)
        {
            throw new NotSupportedException();
        }

        public void Add(TKey key, TValue value)
        {
            throw new NotSupportedException();
        }

        public abstract bool ContainsKey(TKey key);

        public abstract ICollection<TKey> Keys
        {
            get;
        }


        public abstract bool TryGetValue(TKey key, out TValue value);

        public abstract ICollection<TValue> Values
        {
            get;
        }

        ICollection<TValue> IDictionary<TKey, TValue>.Values
        {
            get { return Values; }
        }

        public abstract TValue this[TKey key]
        {
            get;
            set;
        }

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            throw new NotSupportedException();
        }

        public void Clear()
        {
            throw new NotSupportedException();
        }

        public abstract bool Contains(KeyValuePair<TKey, TValue> item);

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            IList<TKey> keys = Keys.ToList<TKey>();
            for (int i = arrayIndex; i < this.Count; i++)
            {
                array[i] = new KeyValuePair<TKey, TValue>(keys[i], this[keys[i]]);
            }
        }

        public virtual int Count
        {
            get { return Values.Count; }
        }

        public bool IsReadOnly
        {
            get { return true; }
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            throw new NotSupportedException();
        }

        public abstract IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        /// 空不可变字典
        /// </summary>
        internal class EmptyImmutableDictionary : ImmutableDictionary<TKey, TValue>
        {
            public override bool TryGetValue(TKey key, out TValue value)
            {
                value = default(TValue);
                return false;
            }

            public override TValue this[TKey key]
            {
                get
                {
                    return default(TValue);
                }
                set
                {
                    throw new NotSupportedException();
                }
            }

            public override int Count
            {
                get { return 0; }
            }

            public override bool ContainsKey(TKey key)
            {
                return false;
            }

            public override bool Contains(KeyValuePair<TKey, TValue> item)
            {
                return false;
            }


            public override IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
            {
                return ImmutableSet<KeyValuePair<TKey, TValue>>.Of().GetEnumerator();
            }

            public override ICollection<TKey> Keys
            {
                get { return ImmutableSet<TKey>.Of(); }
            }


            public override ICollection<TValue> Values
            {
                get { return ImmutableCollection<TValue>.EMPTY_IMMUTABLE_COLLECTION; }
            }

            public override bool Equals(object obj)
            {
                if (obj is IDictionary<TKey, TValue>)
                {
                    IDictionary<TKey, TValue> that = (IDictionary<TKey, TValue>)obj;
                    return that.Count == 0;
                }
                return false;
            }

            public override int GetHashCode()
            {
                return 0;
            }

            public override string ToString()
            {
                return "{}";
            }
        }

        /// <summary>
        /// 包含单个元素的不可变字典
        /// </summary>
        /// <typeparam name="K"></typeparam>
        /// <typeparam name="V"></typeparam>
        internal class SingletonImmutableDictionary<K, V> : ImmutableDictionary<K, V>
        {
            private readonly K singleKey;
            private readonly V singleValue;
            private KeyValuePair<K, V> entry;

            internal SingletonImmutableDictionary(K singleKey, V singleValue)
            {
                this.singleKey = singleKey;
                this.singleValue = singleValue;
            }

            internal SingletonImmutableDictionary(KeyValuePair<K, V> entry)
            {
                this.entry = entry;
                this.singleKey = entry.Key;
                this.singleValue = entry.Value;
            }

            //private KeyValuePair<K, V> KeyValuePair()
            //{
            //    KeyValuePair<K, V> e = entry;
            //    return (e.Equals(default(KeyValuePair<K, V>)))
            //        ? (entry = Maps.immutableEntry(singleKey, singleValue)) : e;
            //}

            public override V this[K key]
            {
                get
                {
                    return singleKey.Equals(key) ? singleValue : default(V);
                }
                set
                {
                    throw new NotSupportedException();
                }
            }

            public override int Count
            {
                get { return 1; }
            }

            public override bool ContainsKey(K key)
            {
                return singleKey.Equals(key);
            }

            public override bool Contains(KeyValuePair<K, V> item)
            {
                return singleKey.Equals(item.Key) && singleValue.Equals(item.Value);
            }

            private ImmutableSet<K> keySet;

            public override ICollection<K> Keys
            {
                get
                {
                    ImmutableSet<K> ks = keySet;
                    return (ks == null) ? (keySet = ImmutableSet<K>.Of(singleKey)) : ks;
                }
            }

            private ImmutableCollection<V> values;

            public override bool TryGetValue(K key, out V value)
            {
                if (singleKey.Equals(key))
                {
                    value = singleValue;
                    return true;
                }
                value = default(V);
                return false;
            }

            public override ICollection<V> Values
            {
                get
                {
                    ImmutableCollection<V> v = values;
                    return (v == null) ? (values = new VValues(singleValue)) : v;
                }
            }

            private class VValues : ImmutableCollection<V>
            {
                readonly V singleValue;

                internal VValues(V singleValue)
                {
                    this.singleValue = singleValue;
                }

                public override bool Contains(V item)
                {
                    return singleValue.Equals(item);
                }

                public override int Count
                {
                    get
                    {
                        return 1;
                    }
                }

                public override bool IsEmpty
                {
                    get
                    {
                        return false;
                    }
                }

                public override IEnumerator<V> GetEnumerator()
                {
                    return ImmutableSet<V>.Of(singleValue).GetEnumerator();
                }
            }

            public override bool Equals(object obj)
            {
                if (obj == this)
                {
                    return true;
                }
                if (obj is IDictionary<TKey, TValue>)
                {
                    IDictionary<TKey, TValue> that = (IDictionary<TKey, TValue>)obj;
                    if (that.Count != 1)
                    {
                        return false;
                    }
                    IEnumerator<KeyValuePair<TKey, TValue>> itera = that.GetEnumerator();
                    itera.MoveNext();
                    KeyValuePair<TKey, TValue> entry = itera.Current;
                    return singleKey.Equals(entry.Key)
                        && singleValue.Equals(entry.Value);
                }
                return false;
            }

            public override int GetHashCode()
            {
                return singleKey.GetHashCode() ^ singleValue.GetHashCode();
            }

            public override string ToString()
            {
                return new StringBuilder()
                    .Append('{')
                    .Append(singleKey.ToString())
                    .Append('=')
                    .Append(singleValue.ToString())
                    .Append('}')
                    .ToString();
            }

            public override IEnumerator<KeyValuePair<K, V>> GetEnumerator()
            {
                return ImmutableSet<KeyValuePair<K, V>>.Of(new KeyValuePair<K, V>(singleKey, singleValue)).GetEnumerator();
            }
        }

        private class EntrySet : ImmutableSet<KeyValuePair<TKey, TValue>>.ArrayImmutableSet<KeyValuePair<TKey, TValue>>
        {
            readonly RegularImmutableDictionary map;

            internal EntrySet(RegularImmutableDictionary map)
                : base(map.entries)
            {
                this.map = map;
            }

            public override bool Contains(KeyValuePair<TKey, TValue> target)
            {
                KeyValuePair<TKey, TValue> entry = (KeyValuePair<TKey, TValue>)target;
                TValue mappedValue = map[entry.Key];
                return mappedValue != null && mappedValue.Equals(entry.Value);
            }
        }


        private class KeySet: ImmutableSet<KeyValuePair<TKey, TValue>>.TransformedImmutableSet<KeyValuePair<TKey, TValue>, TKey>
        {
            readonly RegularImmutableDictionary map;

            internal KeySet(RegularImmutableDictionary map)
                : base(map.entries, map.keySetHashCode)
            {
                this.map = map;
            }

            internal override TKey Transform(KeyValuePair<TKey, TValue> element)
            {
                return element.Key;
            }

            public override bool Contains(TKey target)
            {
                return map.ContainsKey(target);
            }
        }

        private class VValues : ImmutableCollection<TValue>
        {
            readonly RegularImmutableDictionary map;

            internal VValues(RegularImmutableDictionary map)
            {
                this.map = map;
            }

            public override int Count
            {
                get { return map.entries.Length; }
            }

            public override bool IsEmpty
            {
                get
                {
                    return false;
                }
            }
            public override bool Contains(TValue target)
            {
                return map.Values.Contains(target);
            }

            public override IEnumerator<TValue> GetEnumerator()
            {
                return map.Values.GetEnumerator();
            }
        }

        internal class RegularImmutableDictionary: ImmutableDictionary<TKey, TValue>
        {
            internal readonly KeyValuePair<TKey, TValue>[] entries; // entries in insertion order
            internal readonly object[] table; // alternating keys and values
            // 'and' with an int then shift to get a table index
            internal readonly int mask;
            internal readonly int keySetHashCode;

            internal RegularImmutableDictionary(params KeyValuePair<TKey, TValue>[] entries)
            {
                // each of our 6 callers carefully put only Entry<K, V>s into the array!
                KeyValuePair<TKey, TValue>[] tmp = entries;
                this.entries = tmp;

                int tableSize = Hashing.ChooseTableSize(entries.Length);
                table = new object[tableSize * 2];
                mask = tableSize - 1;

                int keySetHashCodeMutable = 0;
                foreach (KeyValuePair<TKey, TValue> entry in this.entries)
                {
                    TKey key = entry.Key;
                    int keyHashCode = key.GetHashCode();
                    for (int i = Hashing.Smear(keyHashCode); true; i++)
                    {
                        int index = (i & mask) * 2;
                        object existing = table[index];
                        if (existing == null)
                        {
                            TValue value = entry.Value;
                            table[index] = key;
                            table[index + 1] = value;
                            keySetHashCodeMutable += keyHashCode;
                            break;
                        }
                        else if (existing.Equals(key))
                        {
                            throw new ArgumentException("duplicate key: " + key);
                        }
                    }
                }
                keySetHashCode = keySetHashCodeMutable;
            }

            public override TValue this[TKey key]
            {
                get
                {
                    if (key == null)
                    {
                        return default(TValue);
                    }
                    for (int i = Hashing.Smear(key.GetHashCode()); true; i++)
                    {
                        int index = (i & mask) * 2;
                        object candidate = table[index];
                        if (candidate == null)
                        {
                            return default(TValue);
                        }
                        if (candidate.Equals(key))
                        {
                            // we're careful to store only V's at odd indices
                            TValue value = (TValue)table[index + 1];
                            return value;
                        }
                    }
                }
                set
                {
                    throw new NotSupportedException();
                }
            }

            public override int Count
            {
                get
                {
                    return entries.Length;
                }
            }

            public override bool ContainsKey(TKey key)
            {
                return !this[key].Equals(default(TValue));
            }

            private ImmutableSet<TKey> keySet;

            public override ICollection<TKey> Keys
            {
                get
                {
                    ImmutableSet<TKey> ks = keySet;
                    return (ks == null) ? (keySet = new KeySet(this)) : ks;
                }
            }


            private ImmutableCollection<TValue> values;

            public override ICollection<TValue> Values
            {
                get
                {
                    ImmutableCollection<TValue> v = values;
                    return (v == null) ? (values = new VValues(this)) : v;
                }
            }

            public override bool TryGetValue(TKey key, out TValue value)
            {
                if (ContainsKey(key))
                {
                    value = this[key];
                    return true;
                }
                value = default(TValue);
                return false;
            }

            public override bool Contains(KeyValuePair<TKey, TValue> item)
            {
                foreach (TKey k in Keys)
                {
                    if (k.Equals(item.Key) && this[k].Equals(item.Value))
                        return true;
                }
                return false;
            }

            private ImmutableSet<KeyValuePair<TKey, TValue>> entrySet;

            public override IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
            {
                ImmutableSet<KeyValuePair<TKey, TValue>> es = entrySet ?? new EntrySet(this);
                return es.GetEnumerator();
            }

            public override string ToString()
            {
                StringBuilder result = new StringBuilder(Count * 16)
                    .Append('{')
                    .Append(entries[0]);
                for (int e = 1; e < entries.Length; e++)
                {
                    result.Append(", ").Append(entries[e].ToString());
                }
                return result.Append('}').ToString();
            }
        }

    }
}
